# 79. 单词搜索
from typing import List


# 79. 单词搜索
# 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
def exist(board: List[List[str]], word: str) -> bool:
    pos_list = list()

    board_width = len(board[0])
    board_height = len(board)

    def back_track(current_word_index: int,
                   board_row: int,
                   board_column: int) -> bool:

        # 字符已经全部找齐
        if current_word_index >= len(word):
            return True

        # 搜索越界的情况
        if not (0 <= board_row <= (board_height - 1) and 0 <= board_column <= (board_width - 1)):
            return False

        # 当前查找的字符
        current_word = word[current_word_index]
        board_word = board[board_row][board_column]

        # 搜索到符合条件的字符
        # 用过的字母不能重复使用
        if current_word == board_word and (board_row, board_column) not in pos_list:
            pos_list.append((board_row, board_column))
            current_word_index += 1

            # 上
            top = back_track(current_word_index, board_row - 1, board_column)
            # 下
            down = back_track(current_word_index, board_row + 1, board_column)
            # 左
            left = back_track(current_word_index, board_row, board_column - 1)
            # 右
            right = back_track(current_word_index, board_row, board_column + 1)

            current_word_index -= 1
            pos_list.pop()
            # 只要任何一个为 true，就可以继续往下搜索
            return top or down or left or right
        return False

    # 利用双重循环标注起始点
    for row in range(board_height):
        for column in range(board_width):
            re = back_track(0, row, column)
            if re:
                return re
    return False


board_1 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
word_1 = "ABCCED"
result = exist(board_1, word_1)
print(f"result:{result}")

board_1 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
word_1 = "SEE"
result = exist(board_1, word_1)
print(f"result:{result}")

board_1 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
word_1 = "ABCB"
result = exist(board_1, word_1)
print(f"result:{result}")

board_1 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]
word_1 = "EEDA"
result = exist(board_1, word_1)
print(f"result:{result}")
